Some embodiments of the invention described may relate to computer graphics, and in particular, to illumination.
Stated generally, computer graphics rendering is a process by which graphics instructions and data are received and processed so that image data is produced. This image data may then be sent to an input/output device (I/O) such as a display. Rendering creates data that may be displayed as an image. The resulting image (or set of resulting images) that is displayed in aggregate at a given point in time is known as a scene. A scene represents a computer rendering of what a camera or viewer might see at a given moment in time.
Rendering may include a number of processes, one of which is ray tracing. In ray tracing, the path taken by a ray of light through a scene may be traced, as the ray undergoes reflection, refraction, and/or absorption whenever it touches an object in the scene. For example, given a light source, a ray of light may be traced to some surface, which may be transparent but may refract the light ray in a different direction while absorbing some of the spectrum and altering the color at the surface. From this point, the ray may impinge on another surface that may not be transparent. Here the light may undergo both absorption (which may further change the color) and reflection (which changes the direction). From the second surface, the ray may be reflected into a virtual camera where its color may contribute to a final rendered image. Because ray tracing may take into account such phenomena as reflection and shadows, this method may offer considerable realism compared to other rendering methods.
One particular rendering technique based on ray tracing technique is photon mapping. Traditional ray tracing is able to capture local illumination. Photon mapping may allow simulation of aspects of global illumination, such as refraction of light through a transparent substance, inter-reflections between illuminated objects, and some of the effects caused by atmospheric particulate matter such as smoke or vapor. With photon mapping, light packets (i.e., photons) may be into a scene from a light source. Whenever they intersect a surface, the three dimensional coordinates of the intersection may be stored in a cache, sometimes called the photon map. In addition, the incoming direction of the photon and the energy of the photon may be stored. As each photon is reflected or refracted by intermediate surfaces, the energy of the photon may diminish until no more is left. The path of the photon is then no longer traced. Alternatively, the tracing may be stopped after some predefined number of reflections, in order to save processing time.
Traditional photon mapping may use a single list of photons that is organized using one relatively large topological structure. One such structure that can be utilized for this is a kd-tree. A kd-tree may be viewed as a hierarchical partitioning of a space into cells, such that no cell has an excessive number of items (in this case, photons). Each node of the tree is defined by a plane through one of the dimensions that partitions the set of items into left/right (or up/down) sets, each set having half the items of the parent node. These children are again partitioned into equal halves, using planes through a different dimension. Partitioning stops after a some number of levels with each item in its own cell, i.e., associated with its own leaf. Creating a kd-tree for a single large set of photons (e.g., a kd-tree of tens of millions of photons) may be computationally expensive and difficult to efficiently search. Accordingly, such a kd-tree may become a bottleneck for processing purposes.